All Questions
Tagged with ds.algorithmscounting-complexity
28 questions
3votes
1answer
90views
What is the fastest algorithm for computing exact network reliability?
In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i....
- 696
10votes
0answers
165views
Fastest Known Algorithm to Count Acyclic Orientations in a Graph
Given an undirected graph $G$, an acyclic orientation of $G$ is choice of orientation for each edge of $G$ (turning each edge into an arc) such that the resulting directed graph has no directed cycles....
- 696
3votes
0answers
60views
Counting subsets of bipartite graph part which admit an induced perfect matching
Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
4votes
0answers
232views
On solving Planar Circuit SAT
This enquiry is three-sided. Side 1 - State of the art Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$? Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...
- 6,952
2votes
0answers
54views
The Edge Cover Equilibrium Problem
Let the Edge Cover Equilibrium Problem be the following: INPUT: a simple undirected graph $G$. OUTPUT: YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
- 6,952
0votes
0answers
136views
On permanent mod $3^t$ computation
By $'$ I mean transpose. I gather the info here from rjlipton.wordpress.com/2014/12/21/modulating-the-permanent. We know that if $U\in\Bbb F_{3^t}^{n\times n}$ satisfies $UU'=I_n$ in $\Bbb F_{3^t}$ ...
- 13.5k
0votes
1answer
233views
What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?
We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$. We also know there are degree $3$...
- 13.5k
11votes
3answers
860views
Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)
In a read-twice opposite CNF formula each variable appears twice, once positive and once negative. I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of ...
- 6,952
6votes
1answer
390views
FPRAS on #P complete problems and self reducibility
I am quoting a phrase of Martin Dyer in his paper Approximate Counting by Dynamic Programming: Since 0-1 knapsack is self-reducible, existence of an fpras for the problem now follows indirectly from ...
- 447
17votes
1answer
2kviews
The complexity of counting simple paths in a directed graph
Let $G$ be a digraph (not necessarily a DAG) and let $s,t \in V(G)$. What is the complexity of counting the number of simple $s-t$ paths in $G$. I would expect the problem to be #${\mathsf P}$-...
- 2,327
17votes
2answers
641views
Can we approximate the number of words accepted by an NFA?
Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
- 9,548
7votes
2answers
461views
What are the current best upper bounds of #P?
#P is the class of counting problems for problems in NP. In other words, a solution to #P returns the number of solutions to a particular problem in NP. I'm wondering if there have been any studies ...
- 2,110
4votes
1answer
726views
Number of subgraphs with given edge parity
I would like to know whether counting number of induced (full) subgraphs (of an undirected graph) that have even number of edges is P or #P-complete. Additionally, is the problem easier if we assume ...
- 43
9votes
2answers
570views
The ODD EVEN DELTA problem
Let $G = ( V, E )$ be a graph. Let $k \leq |V|$ be an integer. Let $O_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an odd number of edges. Let $E_k$ be the number of edge ...
- 6,952
5votes
1answer
775views
Number of subgraphs with a given number of nodes
Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$. The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where $V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$ ...
- 6,952
